A wide range of methods and algorithms are available for compression of digital images and, particularly, the image data corresponding to the pixels in a digital image. The different available methods and algorithms are typically suited to particular types of digital images. An example of such particularized suitability is the JPEG compression standard, which is a widely-adopted standard compression algorithm that is based upon the discrete cosine transform (DCT). JPEG compression and the DCT are described in, for example, Introduction to Data Compression by Khalid Sayood, Morgan Kaufmann Publishers, Inc., San Francisco, Calif., 336–348, 1996.
JPEG compression applies the DCT to image data corresponding to successive 8×8 blocks of pixels. The DCT is effective and efficient with regard to linear correlations that arise over each 8×8 block of pixels. Digital images with these characteristics might include images that correspond to photographs or images with relatively large regions of similar color or tone. Images corresponding to photographs typically include a substantially continuous range of image tones represented by binary values of 24-bits or more. In many such continuous-tone digital images, the variations within the range of image tones are typically well accommodated by the DCT in JPEG compression. Images with relatively large regions of the same color or tone have no changes in tone over those regions and may be effectively compressed by JPEG compression, as well as other compression methods.
It will be appreciated, however, that continuous-tone images are not the only types of digital images. In some applications, digital images may include a smaller range of discrete image colors or tones (e.g., represented by 8-bits, or fewer) or localized high frequency variations such as text elements or other image discontinuities. These types of discrete-tone images, sometimes called palettized images, arise in a variety of applications including, for example, training or help-screen images for software that uses widowed or other graphical user interfaces, shared whiteboards or application sharing, online training, simple animations, etc. The images that arise in such applications are often inefficiently encoded by JPEG compression due to the spatially localized high frequency and discontinuous features in the images.
The present invention includes an adaptive entropy coder coupled with a localized conditioning context to provide efficient compression of discrete-tone images with localized high frequency variations. In one implementation, an arithmetic coder can be used as the adaptive entropy coder.
The localized conditioning context includes a basic context region with multiple context pixels that are adjacent the current pixel, each of the context pixels having an image tone. A state is determined for the basic context region based upon the pattern of unique image tones among the context pixels therein. An extended context region that includes the basic context region is used to identify a non-local trend within the context pixels and a corresponding state. The current pixel is then encoded as having one of the tones in the context or as a not-in-context element. In one implementation, a not-in-context element may be represented by a tone in a color cache that is arranged as an ordered list of most recent not-in-context values.
Statistics for conditional probabilities are gathered for each context during encoding. Many traditional context-based coders choose contexts that are based on the values present in the surrounding context. Since the number of states in the coder grows exponentially with the size of the context, traditional context-based coders work well only when the possible set of values is small (e.g. black and white or binary images), or when the context is very small (one element).
The present invention allows the use of a large context (e.g., up to at least six elements) with elements that can take on many values. This is performed by quantizing the huge number of fundamental states (about 300 trillion) into a set of meaningful patterns (e.g., 60) that are based on the number of unique image tones or values. These patterns model palettized images well. Quantizing the states into this set of meaningful patterns, rather than scalar quantizing the values of the elements, as is traditionally done, greatly increases the efficiency with which palettized images can be encoded or compressed.
Additional objects and advantages of the present invention will be apparent from the detailed description of the preferred embodiment thereof, which proceeds with reference to the accompanying drawings.